import java.util.HashMap;
import java.util.Map;

/**
 * @author LKQ
 * @date 2022/3/5 14:17
 * @description 同余定理：如果两个整数m、n满足n-m能被k整除，那么n和m对k同余
 * （j的前缀和 - i的前缀和 ） % k == 0 ==> j的前缀和 % k == i的前缀和 % k
 */
public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = {23, 2,4,6,7};
        solution.checkSubarraySum(nums, 6);
    }
    public boolean checkSubarraySum(int[] nums, int k) {
        int m = nums.length;
        if (m < 2) {
            return false;
        }
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        map.put(0, -1);
        int remainder = 0;
        for (int i = 0; i < m; i++) {
            remainder = (remainder + nums[i]) % k;
            if (map.containsKey(remainder)) {
                int prevIndex = map.get(remainder);
                if (i - prevIndex >= 2) {
                    return true;
                }
            } else {
                map.put(remainder, i);
            }
        }
        return false;
    }
}
